package 每日一题;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-22
 **/

public class No397整数替换 {

    /**
     * 给定一个正整数 n ，你可以做如下操作：
     * 如果 n 是偶数，则用 n / 2替换 n 。
     * 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
     * n 变为 1 所需的最小替换次数是多少？
     * <p>
     * 示例 1：
     * 输入：n = 8
     * 输出：3
     * 解释：8 -> 4 -> 2 -> 1
     * 示例 2：
     * 输入：n = 7
     * 输出：4
     * 解释：7 -> 8 -> 4 -> 2 -> 1
     * 或 7 -> 6 -> 3 -> 2 -> 1
     * 示例 3：
     * 输入：n = 4
     * 输出：2
     *  
     * 提示：
     * 1 <= n <= 231 - 1
     */

    public int integerReplacement(int n) {
        int result = this.dfs(n);
        return result;
    }

    private int dfs(long n) {
        /**
         * 可以使用map加快速度
         */
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return this.dfs(n / 2) + 1;
        } else {
            // 这里加1会溢出,所以使用long
            return Math.min(this.dfs(n - 1), this.dfs(n + 1)) + 1;
        }
    }

    // 错误的Bad爆内存解法
    public int err_OOM_integerReplacement(int n) {

        int t = 5;

        if (((long) n + (long) t) <= Integer.MAX_VALUE) {
            n = n + t;
        }

        // 超出内存限制...OOM
        int[] dp = new int[n];

        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 2;

        for (int i = t; i <= (n - t); i++) {
            if (i % 2 != 0) {
                // 奇数
                int x = Math.min(dp[(i + 1) / 2], dp[(i - 1) / 2]) + 2;
                int y = dp[i - 1] + 1;
                dp[i] = Math.min(x, y);
            } else {
                // 偶数
                dp[i] = dp[i / 2] + 1;
            }
        }

        return dp[n - t];
    }

    public static void main(String[] args) {
        No397整数替换 n = new No397整数替换();
        int result = n.integerReplacement(Integer.MAX_VALUE);
        System.out.println(result);
    }

}
